The present invention relates to a high speed parallel data processing system and, more particularly, to a parallel data processing system comprised of an array of identical interconnected cells operating under the control of a master controller to operate on single bits of data. Even more particularly, the present invention pertains to implementation of superresolution image enhancement in the Geometric Arithmetic Parallel Processor (GAPP), a Single Instruction-Multiple Datastream (SIMD) array processor, and provides real-time superresolution image enhancement processing.
The possibility of superresolution images, namely, images having better resolution than that obtained from purely linear geometrical considerations, was discovered in the early fifties. Since then superresolution algorithmic development and greatly increased computing power have made the technique practical. A recent example is the restoration of the Hubble space telescope imagery performed by NASA teams.
The superresolution image enhancement approach to real-time image processing is an example of certain data processing tasks that require that substantially identical logical or arithmetic operations be performed on large amounts of data. One approach to carrying out such tasks which is drawing increasing attention is parallel processing. In parallel processing, each element or cell of an array processor made up of such cells processes its own bit of data at the same time as all other cells of the array processor perform the same process on their own bit of data. Such machines are referred to by several names, including Single Instruction-Multiple Datastream (SIMD) array processors.
A common arrangement for such a machine is as a rectangular array of cells, with each interior cell connected to its four nearest neighboring cells and each edge cell connected to a data input/output device. Each cell is connected as well to a master controller which coordinates the movement of data through the array by providing appropriate instructions to the processing elements. Such an array proves useful, for example, in high resolution image processing. The image pixels comprise a data matrix which can be loaded into and processed quickly and efficiently by the processor array.
Although based upon the same genetic concept of an array of cells all performing the same function in unison, parallel processors vary in details of cell design. For example, U.S. Pat. No. 4,215,401 to Holsztynski et al. discloses a cell which includes a random access memory (RAM), a single bit accumulator, and a simple logical gate. The disclosed cell is extremely simple and, hence, inexpensive and easily fabricated. A negative consequence of this simplicity, however, is that some computational algorithms are quite cumbersome so that it may require many instructions to perform a simple and often repeated task.
U.S. Pat. No. 4,739,474, to Holsztynski et al., represents a higher level of complexity, in which the logic gate is replaced by a full adder capable of performing both arithmetic and logical functions. Pressing the full adder into dual service creates an efficiency which more than offsets the added complexity and cost incurred by including a full adder in each cell.
It is important to note that the substitution of a full adder for a logic gate, while superficially simple, is in reality a change of major consequence. The cell structure cannot be allowed to become too complex because in a typical array the cell will be repeated dozens if not hundreds of times. The cost of each additional element in terms of money and space on a VLSI chip is therefore multiplied many times. It is therefore no simple matter to identify those functions which are sufficiently useful to justify their incorporation into the cell. It is similarly no simple matter to implement those functions so that their incorporation is not realized at too high a cost.
Parallel processors may also vary in the manner of cell interconnection. As mentioned above, cells are typically connected to their nearest physical neighbors. All cells except those at the edge of the entire array are connected to four neighbors. It has not heretofore been completely appreciated, however, that significant benefits may flow from providing for alternate paths of interconnection and, specifically, in providing programmable, flexible interconnection between cells.
General mathematical properties of image enhancement and other digital image processing techniques are presented, for example, in Digital Image Processing (Addison-Wesley, 1992) by R. Gonzalez and R. Woods. General techniques useful in optics are presented, for example, in Optics (Addison-Wesley, 1974) by E. Hecht and A. Zajac. For the purposes of further background, the following additional references are noted: Image Recovery: Theory and Application (Academic Press, 1988) by Henry Stark; Deconvolution with Applications in Spectroscopy (Academic Press, 1984) by Peter Jansson (which is incorporated herein by reference); "Resolution Enhancement of Spectra," J. Opt. Soc. Am., May 1970, vol. 60, by Peter A. Jansson et at.; "Survey of recent developments in digital image restoration," Opt. Eng., May 1990, vol. 29, by Sezan and Tekalp; "Restoring with Maximum Likelihood and Maximum Entropy," J. Opt. Soc. Am., vol. 62, pp. 511-18, by B. R. Frieden; "Image Restoration by Discrete Deconvolution of Minimal Length," J. Opt. Soc. Am., vol. 64, pp. 682-86, by B. R. Frieden; "Image reconstruction from incomplete and noisy data," Nature, vol. 272, pp. 686-90, by S. F. Gull and G. J. Daniell; "The relationship between image restoration by the maximum a posteriori method and a maximum entropy method,' IEEE Trans. Acoust. Speech Sig. Proc., ASSP-28(1), pp. 114-17 (1980), by H. J. Trussell; "Entropy-based algorithm for reducing artifacts in image restoration," Opt. Eng., vol. 26(7), pp. 617-22 (1987), by R. A. Consalves and H.-M. Kuo; and "Image restoration by a powerful maximum entropy method," Comp. Vision Graph. Image Proc., vol. 23, pp. 113-28 (1983), by S. F. Burch, S. F. Gull, and J. Skilling; "Iterafive Noncoherent Angular Superresolution," Proc. IEEE, pp. 100-05, June 1988, by Mark A. Richards (which is incorporated herein by reference).
The classical limit for visual optical systems to separate point objects is given approximately by R = .lambda./d, where R is the Rayleigh distance, .lambda. is the wavelength of light, and d is the optical aperture. For machine systems, the limit is two to four times greater because the objects need to be nearly completely separated so that amplitude and position may be accurately measured. Superresolution techniques can be used to recover lost resolution, but practical requirements have made prior real-time implementations impractical because of the following requirements:
1. High magnification (approximately five samples across the Airy disk) is required to achieve a non-aliased image. Usually this results in an impractical small optical field-of-view.
2. A sensitive focal plane array with a large number of pixels to compensate for the high required magnification.
3. Fast processing algorithms and hardware to achieve superresolution in real time.
4. Highly uniform focal plane arrays to avoid fixed pattern noise and dead pixels.
It is therefore desireable to provide techniques and devices that satisfy these requirements.